# -*- coding: utf-8 -*-            
# @Time : 2023/8/9 22:30
# @Author  : lining
# @FileName: 树的直径.py
"""
一棵无向树，不知道谁是父节点谁是子节点，求这棵树上两个最远的点之间的距离
n个点，n-1条边
https://leetcode.cn/problems/tree-diameter/
输入edgs=[[0,1],[0.2]]
表示.可以0做根节点，[0,1],[0,2]做边，也可以1做根节点，也可以2做根节点
        0
    1        2
[[0,1], [1,2], [2,3], [1,4], [4,5]]
分析：
            0
     1       x        2
             3
从0出发，（1）距离他最远的点，必然是直径的一端，然后从这个点出去去找离他最远的点
反证法，如果3不是不是直径的一端，则必然有另一根线比他长，他们相交于x点，比如1x2。
如果3x比2x短，则0x2比0x3长，与3是距离0最远点的矛盾
如果1x长于3x，则0x1比0x3长，与3是距离0最远的点矛盾
先从一个点出发找离他最远的p，在从p出发找离他最远的点q，pq一定是直径

"""
# 深度
deep = 0
# 下标
sub = 0
# 保存结果
result = []
# 当前做根节点的边
root = 0
def getdiameter(edgs):
    """
    :param edgs: 边
    :return:
    """
    global deep
    global sub
    # 遍历到edgs的结尾，把结果放进去
    if sub+1>len(edgs):
        result.append(deep)
        return
    # 从第二个数开始累计深度
    if sub>0:
        if edgs[sub] == edgs[sub-1]:
            deep = deep+1
    sub = sub+1